import java.util.List;

class ReverseKGroup {

    public static class ListNode {
            int val;
            ListNode next;
            ListNode(int x) { val = x; }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return head;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode p = head;
        ListNode pre = newHead;

        while (p != null){
            int i = 0;
            ListNode tmpNode = new ListNode(0);
            ListNode np = p;
            for (i=0; i<k && np!=null; ++i){
                ListNode tmp = np.next;
                np.next = tmpNode.next;
                tmpNode.next = np;
                np = tmp;
            }

            if (i < k){
                ListNode tmptmpNode = new ListNode(0);
                np = tmpNode.next;

                while (np != null){
                    ListNode tmp = np.next;
                    np.next = tmptmpNode.next;
                    tmptmpNode.next = np;
                    np = tmp;
                }

                pre.next = tmptmpNode.next;
                break;
            } else {
                pre.next = tmpNode.next;
                ListNode tmp_p = tmpNode.next;
                while(tmp_p != null && tmp_p.next != null){
                    tmp_p = tmp_p.next;
                }
                pre = tmp_p;
            }

            p = np;
        }

        return newHead.next;
    }


    public static void main(String[] args){
        ReverseKGroup obj = new ReverseKGroup();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        ListNode res = obj.reverseKGroup(node1, 2);
        while(res != null){
            System.out.print(res.val + " ");
            res = res.next;
        }
        System.out.println();
    }

}